Generally, spatial entities are represented through electronic maps. An electronic map is a visual representation of spatial entities on an electronic display using certain hardware and software, which is a symbolization process of the spatial entities on the electronic display. The attribute and graphics information associated with a spatial entity for displaying it on an electronic map is known as an element. A point element corresponds to a point entity, a line element corresponds to a line entity, and a plane element corresponds to a plane entity.
The rapid development and extensive application of Geographic Information System (GIS) have led to an explosive increase of spatial data. Especially, the popularization of networking GIS applications has increased the need for network electronic maps displaying the huge amount of spatial entities in a network environment.
The annotation of an element is an important part of the display of the element on an electronic map. Electronic map display has to meet clarity, readability, aesthetic quality, informativeness and high-efficiency requirements. To provide proper element annotation, conflict detection and avoidance of annotations of point, line and plane elements have to be dealt with, which forbid annotations overlying each other, forbid annotations overlying point elements, and require annotations to avoid line elements if permitted.
Existing methods for conflict detection and avoidance of element annotations have the following problems. 1. Low efficiency and multiple accessing of spatial data and attribute data, which cannot meet the requirements for displaying massive spatial data efficiently on an electronic map in a network environment. For example, the conventional local search algorithm reads all related annotations before each geometric computation, and releases them after the computation. 2. Failure to meet functional requirements. For example, the grid-based method, similar to grid-based indexing, calculates the size of a cell according to the size of a character, and divides the screen into a series of cells to form screen indexes (in screen coordinates). However, annotations may have different font sizes, e.g., representative elements and names are generally larger; annotations may be tilted; and annotations are forbidden to overlie point entities and are required to avoid line entities if permitted. All these problems cannot be solved by the grid-based method. In addition, the division of a grid based on the size of a character cannot ensure annotation information of elements is displayed as much as possible, because many annotations that could have been displayed are discarded.